The present invention relates to apparatus for either on-line or off-line testing of an electrical circuit. More particularly, the invention relates to circuit testing apparatus employing a linear feedback shift register ("LFSR") for signature analysis.
Methods and apparatus for testing electrical circuits by "signature analysis" are well known. Commercial devices such as the Hewlett Packard HP 5004A signature analyzer have been available for a number of years. Publications describing such devices and methods of testing include "Hexadecimal Signatures Identify Trouble Spots in Microprocessor Systems" by G. Gordon et al., Electronics Magazine, Mar. 3, 1977, pp. 89-96; "Die Signatur-Analyse" by K. Heine, Elektronik Magazine (1979), Volume 1, pp. 48-51; "Logic-state and Signature Analysis Combine for Fast, Easy Testing" by I. Spector, Electronics Magazine, June 8, 1978, pp. 140-145.
With the signature analysis method of testing, an electrical circuit having an input and an output is connected at its output to a linear feedback shift register (LFSR) and connected at its input to an automatic test pattern generator (ATG). The ATG applies test patterns sequentially to the input of the circuit under test (CUT) for a prescribed number of test cycles. The output signals produced during this test sequence causes the LFSR to pass through a succession of specific states so that, after completion of the test, the LFSR contains a prescribed, known "signature" (bit pattern) if the ATG, the CUT and the LFSR are working properly.
Upon the completion of the test, the bit pattern in the LFSR is compared to the known bit pattern of the correct signature (i.e., the signature of a properly-working CUT) to determine whether any of the elements of the test system (ATG, CUT and LFSR) is faulty.
During the test, the contents of the LFSR change from one "signature" to the next as the LFSR moves through its successive states. For a 16-bit LFSR, for example, there are 2.sup.16 different possible signatures. Normally, however, the LFSR passes through only a small percentage of this maximum number of signatures during a given test.
Even assuming that the ATG and the LFSR hardware itself is functioning properly, the signature analysis method of circuit testing has two basic problems:
(1) It is difficult, if not impossible, to determine when (during which test cycle) the error appeared in the CUT from the final LFSR signature at the completion of the test sequence (assuming that the final signature is incorrect).
(2) It is possible for the LFSR to land in the correct state at the conclusion of a test sequence, indicating the correct signature, even though the CUT is faulty and produces multiple errors.
To understand the latter problem, it is necessary to analyze the error detection capabilities of the LFSR using probabilistic mathematics. It will be assumed, throughout this analysis, that all output symbols produced by the CUT are equally likely and there is no correlation between them. It will be assumed also (1) that the LFSR is designed to produce a maximal length random number sequence if continually presented with null symbols; (2) that the LFSR cannot get into a particular state from two different states upon receipt of the same input symbol and, similarly, (3) that the LFSR can only make a transition from one specific state to another upon receipt of one specific symbol.
Consider a test symbol with an ATG, CUT and LFSR connected together, which passes through N test cycles. The CUT therefore produces a string of N output symbols during the testing procedure which could be a correct sequence a or, in the alternative, an i symbol error sequence, b. b is thus a sequence of N symbols which differs from the sequence a in exactly i positions. It is assumed, in this regard, that all i symbol errors (for any particular value of i) are equally likely.
During the test sequence the LFSR starts in some initial state, S.sub.0, and compresses the string a or b of N symbols. In compressing these symbols, the LFSR will pass through N+1 states in total (including the initial and final states). However, since it is possible that states may be revisited, the number of distinct states may be less than this. We let A.sub.i denote the average number of distinct states visited when a string of i symbols is compressed; we let M denote the total number of LFSR states (e.g., 2.sup.16 for a 16-bit LFSR).
Now, therefore: EQU A.sub.0 =1
(i.e., the initial state) EQU A.sub.i+1 =A.sub.i +P,
where P is the probability that the (i+1).sup.st symbol causes a transition to a state which has not previously been visited. Since all symbols are equally likely, it follows that all next states are equally likely. EQU P=(M-A.sub.i)/M;
i.e., the number of unvisited states divided by the total number of states. EQU A.sub.i+1 =A.sub.i +(M-A.sub.i)/M=A.sub.i (M-1)/M+1
Let EQU .alpha.=(M-1)/M;
and EQU A.sub.i+1 =.alpha.A.sub.i +1
Hence, EQU A.sub.0 =1, A.sub.1 =.alpha.+1, A.sub.2 =.alpha..sup.2 +.alpha.+1, EQU A.sub.i =.alpha..sup.i +.alpha..sup.i-1 + . . . +.alpha..sup.2 +.alpha.+1.
This geometric series can be summed to yield: EQU A.sub.i =(1-.alpha..sup.i+1)/(1-.alpha.)
It follows that the fraction of states visited (on the average) during the compression of i symbols can be written as A.sub.i /M.
In considering the error coverage of the LFSR, it is necessary to define some additional notation:
a.sub.i =the i.sup.th symbol in a; and likewise PA0 b.sub.i =the i.sup.th symbol in b; PA0 S.sub.i (a)=the LFSR state after processing the first i symbols of a; and PA0 S.sub.F (a)=the LFSR state after a has been completely compressed. PA0 P.sub.i =the probability that the LFSR detects an i-symbol error (i.e., an erroneous sequence yields an incorrect signature); and PA0 R.sub.i =the probability that the LFSR does not detect an i-symbol error (i.e., an erroneous sequence yields the correct signature). By definition P.sub.i =1-R.sub.i.
Furthermore,
We wish to determine P.sub.i and R.sub.i for i.gtoreq.1.
Case 1: Consider a 1-symbol error sequence. Let b differ from a in the j.sup.th symbol. EQU S.sub.j-1 (a)=S.sub.j-1 (b)
Since the j.sup.th symbols differ, it follows that EQU S.sub.j (a).noteq.S.sub.j (b).
Now since the string match on all remaining symbols, it follows that EQU S.sub.k (a).noteq.S.sub.k (b),
for all k.gtoreq.j, and hence EQU S.sub.F (a).noteq.S.sub.F (b) EQU P.sub.1 =1 and R.sub.1 =0
Case 2: Consider 2-symbol errors. Let the errors be in positions k and l and assume without loss of generality that k.ltoreq.l. EQU S.sub.k-1 (a)=S.sub.k-1 (b) EQU S.sub.k (a).noteq.S.sub.k (b) EQU S.sub.j (a).noteq.S.sub.j (b),
for k.ltoreq.j.ltoreq.l.
Now since a and b match in all symbols after the l.sup.th symbol, in order for the erroneous string to be accepted (produce the correct final signature), we must have: EQU S.sub.l (a)=S.sub.l (b).
The probability of this occuring given that S.sub.l-1 (a).noteq.S.sub.l-1 (b) and a.sub.l .noteq.b.sub.l is (1/M), where M is the total number of states (symbols) of the LFSR (input alphabet), so that: EQU P.sub.2 =(M-1)/M, R.sub.2 =1/M.
It should be noted that this result is independent of the relative positions of the errors.
Case 3: Consider the general case of i-symbol errors, for i.gtoreq.2. Let the last two symbol errors be in positions k and l, with k.ltoreq.l. Two subcases must be considered.
Case A: S.sub.k (a)=S.sub.k (b). PA1 Case B: S.sub.k (a).noteq.S.sub.k (b).
After compressing the string up to and including the (i-1).sup.st erroneous symbol, the LFSR state matches the corresponding state for the correct sequence.
Hence, it follows that: EQU S.sub.l (a).noteq.S.sub.l (b)
and, since there are no more errors, it follows that EQU S.sub.F (a).noteq.S.sub.F (b).
Hence i-symbol errors of this form will always be detected.
Given this condition, the probability of having S.sub.F (a)=S.sub.F (b) is 1/M, (i.e., the last error may "correct" the state), but the probability that S.sub.k (a)=S.sub.k (b) is simply P.sub.i-1 (i.e., the probability that an (i-1) symbol error is detected): EQU R.sub.i =P.sub.i-1 /M and P.sub.i =1-P.sub.i-1 /M.
It is then a relatively simple matter to show that: ##EQU1##
For M.gtoreq.1, this can be solved to yield: ##EQU2##
For an eight (or more) bit LFSR, P.sub.i can be approximated by: ##EQU3##
It has thus been shown that the signature analysis method of testing an electrical circuit is guaranteed to detect all erroneous strings which differ in exactly one symbol from the correct string. The probability that the LFSR will detect other erroneous string has also been determined and shown to be practically independent of the number of erroneous symbols (once there are more than one) and independent of the relative positions of the erroneous symbols.
There is therefore a finite probability that the LFSR will arrive at a correct final state, although the circuit under test is, in fact, faulty.